package leetcode;

/**
 * description:
 * author:张腾
 * date:2021-06-23
 */
public class leetcode322_2 {
    public static void main(String[] args) {
        System.out.println(new leetcode322_2().coinChange(new int[]{ 2, 3}, 6));
    }
    public int coinChange(int[] coins, int amount) {
        if (amount<1) return 0;
        return resBack(coins,amount,new int[amount]);
    }

    public int resBack(int[] coins,int amount,int count[]){
        if (amount<0)  return -1;
        if (amount==0) return 0;

        if (count[amount-1]!=0) return count[amount-1];

        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = resBack(coins,amount-coin,count);
            if (res >=0 && res < min) min=res+1;
        }
        count[amount-1] = min==Integer.MAX_VALUE? -1:min;
        return count[amount-1];
    }
}
